/**************************************************************************
 * artic.c
 *
 * CECS619 Project 3
 *
 * Authors: Max Stoler, Jason Hatton
 * 
 *************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "artic.h"


#define COLOR_WHITE 0 
#define COLOR_BLACK 1
#define COLOR_GRAY 2


/************************PROTOTYPES***************************************/
static int ArticDFS(Artic *a, int v, int parent);


/************************FUNCTIONS****************************************/

Artic *ArticCreate()
{
	Artic *a; 
	a = (Artic*)malloc(sizeof(Artic));
	if(!a)
	{   
		return 0;
	}
	a->discoverTime = 0;
	a->time = 0;
	a->color = 0;
	a->g = 0;
	return a;
}

void ArticDestroy(Artic *a)
{
	if(a)
	{
		if(a->color)
		{
			free(a->color);
		}
		if(a->g)
		{
			GraphDelete(a->g);
		}
		if(a->discoverTime)
		{
			free(a->discoverTime);
		}
		free(a);
	}
}

static int ArticDFS(Artic *a, int v, int parent)
{
	int w = 0;
	int back = 0;
	int wBack;
	int found = 0; /* More than one child found*/
	a->time++;
	a->discoverTime[v] = a->time;
	back = a->time;
	a->color[v] = COLOR_GRAY;
	
	for(w = 0; w<a->g->size; w++)
	{
		if(GraphGetAdj(a->g, v, w) == 0 || w == parent)
		{
			continue;
		}
		if(a->color[w] == COLOR_WHITE)
		{
			wBack = ArticDFS(a, w, v);				
			if((wBack >= a->discoverTime[v] && parent != -1)
			   || (parent == -1 && found==1))
			{
				printf("Articulation Point: %3d | %s\n", v,
				a->g->vertexNames[v]);
			}
			back = back<wBack?back:wBack;
			found += 1;
		} 
		else if(a->color[w] == COLOR_GRAY)
		{
			back = back<a->discoverTime[w]?back:a->discoverTime[w];
		}
	}
	a->time++;
	a->color[v] = COLOR_BLACK;
	return back;  
}

void ArticFind(Artic*a, Graph*g)
{
	int v;
	a->time = 0;
	a->g = GraphCopy(g);
	a->discoverTime = (int*)malloc(sizeof(int)*g->size);
	if(!a->discoverTime)
	{
		fprintf(stderr, "Out of memory!\n");
		exit(1);
	}		
	a->color  = (int*)malloc(sizeof(int)*g->size);
	if(!a->color)
	{
		fprintf(stderr, "Out of memory!\n");
		exit(1);
	}
	for(v = 0; v<a->g->size; v++)
	{
		a->color[v] = COLOR_WHITE;
	}
	for(v = 0; v<a->g->size; v++)
	{
		a->discoverTime[v] = 0;
	}
	ArticDFS(a, 0, -1);
	free(a->color);
	free(a->discoverTime);
	GraphDelete(a->g);
	a->color = NULL;
	a->discoverTime = NULL;
	a->g = NULL;

	return;
}

